# 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


# 解题思路：如果左根右=右根左，那么这个就是对称的了
# 具体还应该考虑，结构上也要对称，否则如果值都一样就都是返回True了，也就是两个存了结点的数组，每个节点对应的左右节点是否存在也是对称的
# 还要考虑，存的时候，两个数组的节点顺序是刚好相反的，所以是反着比较

# 思路2：层序遍历，每一层中心对称，那就对了
class Solution:
    def __init__(self):
        self.res = []
        self.res1 = []
        self.sol = [[]]
        self.result = True

    def isSymmetrical(self, pRoot):
        # write code here
        self.get_mid(pRoot)
        self.get_right_mid(pRoot)
        try:
            for i in range(len(self.res)):
                if self.res[i] != self.res1[-i - 1]:
                    return False
                if self.res[i].val != self.res1[i].val:
                    return False
                else:
                    if self.res[i].left and not self.res1[i].right:
                        return False
                    if self.res[i].right and not self.res1[i].left:
                        return False

            return True
        except:
            return False

    def get_mid(self, my_root):
        if not my_root:
            return None
        self.get_mid(my_root.left)
        self.res.append(my_root)
        self.get_mid(my_root.right)

    def get_right_mid(self, my_root):
        if not my_root:
            return None
        self.get_right_mid(my_root.right)
        self.res1.append(my_root)
        self.get_right_mid(my_root.left)

    #  解法2：  层序遍历二叉树，可以用这个方法来先存下来每一层的节点，然后遍历这个二维数组，看他每一个小的数组是否中心对称
    def get_level(self, my_root, level):
        if not my_root:
            return None
        else:
            self.sol[level - 1].append(my_root)
            if len(self.sol) == level:
                self.sol.append([])
            self.get_level(my_root.left, level + 1)
            self.get_level(my_root.right, level + 1)

    # 解法2的测试方法，这个用于返回层序遍历的数组，本来想在里面比较，后来发现那样是不对的
    def get_level_adjust(self, my_root, level):
        if my_root == None:
            self.sol[level - 1].append(TreeNode(None))
            return None
        else:
            self.sol[level - 1].append(my_root)
            if len(self.sol) == level:
                # 不能像下面这样，在这里比较，因为这个时候很可能这一层还没有存完!别忘了，这个层序遍历的逻辑是，直到左叶子节点，就开始加一个数组，所以这还根本没完呢
                # for i in range(len(self.sol[level - 1])):
                #     self.res.append('长度:%d'%(len(self.sol[level-1])))
                # try:
                #     if self.sol[level - 1][i].val != self.sol[level - 1][-i - 1].val:
                #         self.result = False
                #         self.res.append('进入了！')
                #         break
                # except:
                #     self.result = False
                #     break
                self.sol.append([])
            self.get_level_adjust(my_root.left, level + 1)
            self.get_level_adjust(my_root.right, level + 1)


# 解法3：递归,这个想法很好的体现上面第一种解法的思想（结构相同，对应位置的值相同），但是其实比第一种方法慢了1ms
def isSymmetrical(self, pRoot):
        # write code here
    if not pRoot:
        return True
    return comRoot(pRoot.left,pRoot.right)
def comRoot(left, right):
    if left == None:
        return right == None;
    if right == None:
        return False;
    if left.val != right.val:
        return False;
    return comRoot(left.right, right.left) and comRoot(left.left, right.right)


node1 = TreeNode(5)
node2 = TreeNode(5)
node3 = TreeNode(5)
node4 = TreeNode(5)
node5 = TreeNode(5)
node6 = TreeNode(5)
node7 = TreeNode(5)

node1.left = node2
node1.right = node3
node2.left = node4
node3.right = node5
node4.left = node6
node5.left = node7

sol = Solution()
# sol.isSymmetrical(node1)
# print(sol.isSymmetrical(node1))
sol.get_level_adjust(node1, 1)
for i in sol.sol:
    for j in range(len(i)):
        if i[j].val != i[-j - 1].val:
            print('不相等啊！')
            break
